#include "BST.h"


namespace STLData {

    int BST::height(BNode* const &ptr) const
    {
        if (ptr == NULL)
            return 0;

        int lt = height(ptr->link[0]), rt = height(ptr->link[1]);

        if (lt < rt)
            return rt + 1;
        return lt + 1;
    }

    BST::BST( )
    {
        nullNode = new BNode;
        nullNode->link[0] = nullNode->link[1] = nullNode;
        nullNode->level = 0;
        root = nullNode;
    }

    BST::BST( const BST & rhs )
    {
        nullNode = new BNode;
        nullNode->link[0] = nullNode->link[1] = nullNode;
        nullNode->level = 0;
        root = clone( rhs.root );
    }

    BST::~BST( )
    {
        makeEmpty( );
        delete nullNode;
    }

    bool BST::isEmpty() const
    {
        return (root == nullNode);
    }

    void BST::makeEmpty( )
    {
        makeEmpty( root );
    }

    int BST::height() const
    {
        return height(root);
    }

    /**
     * Internal method to insert into a subtree.
     * x is the item to insert.
     * t is the node that roots the tree.
     * Set the new root of the subtree.
     */
    void BST::insert( const BNode::Comparable & x, BNode * & t )
    {
        if( t == nullNode )
            t = new BNode( x, nullNode, nullNode );
        else if( compare(x, t->element) )
            insert( x, t->link[0] );
        else if( compare(t->element, x) )
            insert( x, t->link[1] );
        else
            return;  // Duplicate; do nothing

        skew( t );
        split( t );
    }

    /**
     * Internal method to remove from a subtree.
     * x is the item to remove.
     * t is the node that roots the tree.
     * Set the new root of the subtree.
     */
    void BST::remove( const BNode::Comparable & x, BNode * & t )
    {
        static BNode *lastNode, *deletedNode = nullNode;

        if( t != nullNode )
        {
            // Step 1: Search down the tree and set lastNode and deletedNode
            lastNode = t;
            if( compare(x, t->element ))
                remove( x, t->link[0] );
            else
            {
                deletedNode = t;
                remove( x, t->link[1] );
            }

            // Step 2: If at the bottom of the tree and
            //         x is present, we remove it
            if( t == lastNode )
            {
                if( deletedNode == nullNode || desigual(x, deletedNode->element) )
                    return;   // Item not found; do nothing
                deletedNode->element = t->element;
                deletedNode = nullNode;
                t = t->link[1];
                delete lastNode;
            }

            // Step 3: Otherwise, we are not at the bottom; rebalance
            else
                if( t->link[0]->level < t->level - 1 ||
                    t->link[1]->level < t->level - 1 )
                {
                    if( t->link[1]->level > --t->level )
                        t->link[1]->level = t->level;
                    skew( t );
                    skew( t->link[1] );
                    skew( t->link[1]->link[1] );
                    split( t );
                    split( t->link[1] );
                }
        }
    }

    bool BST::igual(const BNode::Comparable lt, const BNode::Comparable rt) {
        dataLine::const_iterator itlt;

        for (itlt=lt.fields.begin();itlt!=lt.fields.end();itlt++) {
            if (*itlt != rt.fields[(*itlt).key()]) {
                return false;
            }
        }
        return true;

    }

    bool BST::compare(const BNode::Comparable lt, const BNode::Comparable rt) {
        dataLine::const_iterator itlt;

        int i = 0;
        for (itlt=lt.fields.begin();itlt!=lt.fields.end();itlt++) {
            if ( sortOrder.size() <= i ) {
                if (*itlt > rt.fields[(*itlt).key()]) {
                    return false;
                }
            } else if (sortOrder[i] == "descending") {
                if (*itlt < rt.fields[(*itlt).key()]) {
                    return false;
                }
            } else {
                if (*itlt > rt.fields[(*itlt).key()]) {
                    return false;
                }
            }
        }
        return true;

    }

// Torsion
    /**
     * Skew primitive for AA-trees.
     * t is the node that roots the tree.
     */
    void BST::skew( BNode * & t )
    {
        if( t->link[0]->level == t->level )
            rotateWithLeftChild( t );
    }

    /**
     * Split primitive for AA-trees.
     * t is the node that roots the tree.
     */
    void BST::split( BNode * & t )
    {
        if( t->link[1]->link[1]->level == t->level )
        {
            rotateWithRightChild( t );
            t->level++;
        }
    }

    void BST::rotateWithLeftChild( BNode * & k2 )
    {
        BNode *k1 = k2->link[0];
        k2->link[0] = k1->link[1];
        k1->link[1] = k2;
        k2 = k1;
    }

    void BST::rotateWithRightChild( BNode * & k1 )
    {
        BNode *k2 = k1->link[1];
        k1->link[1] = k2->link[0];
        k2->link[0] = k1;
        k1 = k2;
    }

    void BST::makeEmpty( BNode * & t )
    {
        if( t != nullNode )
        {
            makeEmpty( t->link[0] );
            makeEmpty( t->link[1] );
            delete t;
        }
        t = nullNode;
    }

    void BST::inorderTree( BNode *t ) const
    {
        if( t != nullNode )
        {
            inorderTree( t->link[0] );
            file->sputn(t->element.fileLine.c_str(), t->element.fileLine.size());
            file->sputc('\n');
            inorderTree( t->link[1] );
        }
    }

}
